package com.aqie.easy.geometric;

import java.util.Arrays;

/**
 * todo
 * 812 最大三角形面积
 * p = (a + b + c)/2
 *  s = sqrt(p*(p-a)*(p-b)*(p-c))
 *
 *  A(n,m) = n! / (n-m)!
 *  C(n,m) = n! / (n-m)!m!
 */
public class LargestTriangleArea {
    public double largestTriangleArea(int[][] points) {
        int length = points.length;
        double p ;
        double s ;
        double ans = 0;
        for (int i = 0; i < length-2; i++){
            for (int j = i + 1; j < length - 1; j ++){
                for (int k = j + 1; k < length; k++){
                    double a = getLength(points[i],points[j]);
                    double b = getLength(points[i], points[k]);
                    double c = getLength(points[j], points[k]);

                    p = (a + b + c) / 2;
                    s = Math.sqrt( p * (p - a) * (p - b) * (p - c));
                    ans = (ans < s) ? s : ans;
                }
            }
        }
        return ans;
    }

    private static double getLength(int[] a, int[] b){
        return Math.sqrt(Math.pow((a[0] - b[0]),2) + Math.pow((a[1] - b[1]), 2));
    }

    public static void main(String[] args) {
        System.out.print(getLength(new int[]{0,0}, new int[]{3,4}));
        int[] arr = {1,2,3,4};
        int l = arr.length;
        permutation(arr, 0, l);
    }

    /**
     * 全排列
     * @param a
     * @param l
     * @param r
     */
    public static void permutation(int[] a, int l, int r){
        int i = 0;
        int tmp = 0;
        if (l < r - 1){
            permutation(a, l + 1, r);
            for (i = (l + 1); i < r; i++){
               tmp = a[l];
               a[l] = a[i];
               a[i] = tmp;

               permutation(a, l + 1, r);
                tmp = a[l];
                a[l] = a[i];
                a[i] = tmp;
            }
        }else {
            printResult(a);
        }
    }

    public static void printResult(int[] res){
       System.out.println(Arrays.toString(res));
    }
}
